ON TREE REPRESENTATION OF READ-ONCE FUNCTIONS IN EXTENDED ELEMENTARY BASES 

Kaftan Dar'ya Vladimirovna, Engineer, faculty of calculus mathematics and cybernetics, Lomonosov Moscow State University (1/52 Leninskie gory street, Moscow, Russia), blond.programmist@gmail.com

517.718.7

10.21685/2072-3040-2017-3-4

Background. The mathematics of Booleand functions has a profound effect in the area of information technologies. This article is devoted to an important ability of the function to be represented in the given basis via a formula without replication of variables (a read-once formula). Functions which can be represented such way may be regarded as quite simply structured in this basis. We consider a problem ofread-once functions’ tree representation in the bases consisting of conjunction, disjunction, negation and polarized Stecenko’s functions. The object of the article is to provide a tree representation where equal functions have isomorphic trees and obtaina set of relevant equivalent tree transformations.
Materials and methods. We apply the mathematics of permutations and useproperties of polirized Stecenko’s functions and labeled rooted trees.
Results and conclusion. We have provided a tree representation for read-oncefunctions in the bases consisting of polarized Stecenko’s functions and an elementarybasis aand corresponding to formulas with raised negotiations, as well as obtaineda set of relevant equivalent transformations for the given type of trees.

read-once function, canonical tree

1. Stetsenko V. A. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. 1992, iss. 4, pp. 139–177.
2. Voronenko A. A. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. 2002, iss. 11, pp. 163–176.
3. Voronenko A. A. Diskretnaya matematika [Discrete mathematics]. 2005, vol. 17, no. 2, pp. 139–143.
4. Dzhevons S. Osnovy nauki [Foundations of science]. Transl. by M. Antonovich. Saint-Petersburg: Izd-vo L. F. Panteleeva, 1881, 744 p.
5. Kuznetsov A. V. Trudy matematicheskogo instituta AN SSSR [Proceedings of the mathematical institute of AS USSR]. 1958, vol. 51, pp. 186–225.